package com.suanfa.sort;

/**
 * Created by buguniao on 16/2/21.
 */
public class QuickSort3Way extends SuanFaTemplate {
    public static void main(String[] args) {
        QuickSort3Way quickSort = new QuickSort3Way();
        double[] arr = quickSort.getRandomArray(1000000000);
        long time = quickSort.run(arr);
        System.out.println("time cost : " + time);
    }

    @Override
    public long run(double[] arr) {
        long t1=System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long t2=System.currentTimeMillis();
        return t2-t1;
    }
    public void sort(double[] arr,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int lt=lo;
        int gt=hi;
        int i=lo+1;

        double v = arr[lo];

        while(i<=gt){
            if(arr[i]>v){
                exchange(arr,i,gt--);
            }else if(arr[i]<v){
                exchange(arr,lt++,i++);
            }else{
                i++;
            }
        }
        sort(arr,lo,lt-1);
        sort(arr,gt+1,hi);
    }
}
